<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html>
<head>
  <meta name="generator" content=
  "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org">

  <title>Complexity</title>
  <link href="cppreference.css" rel="stylesheet" type="text/css">
</head>

<body>
<table>
  <tr>
  <td>
  <div class="body-content">

  <div class="header-box">
    <a href="index.html">cppreference.com</a> &gt; Complexity
  </div>

  <h3>Complexity</h3>

  <p>There are different measurements of the speed of any given
  algorithm. Given an input size of <strong>N</strong>, they can be
  described as follows:</p>

  <table class="misc-table">
    <tr>
      <th>Name</th>

      <th>Speed</th>

      <th>Description</th>

      <th>Formula</th>
    </tr>

    <tr class="misc-table-tr-2">
      <td class="misc-table-td">exponential time</td>

      <td class="misc-table-td">slow</td>

      <td class="misc-table-td">takes an amount of time proportional to a constant raised to
      the <strong>N</strong>th power</td>

      <td class="misc-table-td">K^<strong>N</strong></td>
    </tr>

    <tr class="misc-table-tr-1">
      <td class="misc-table-td">polynomial time</td>

      <td class="misc-table-td">fast</td>

      <td class="misc-table-td">takes an amount of time proportional to <strong>N</strong>
      raised to some constant power</td>

      <td class="misc-table-td"><strong>N</strong>^K</td>
    </tr>

    <tr class="misc-table-tr-2">
      <td class="misc-table-td">linear time</td>

      <td class="misc-table-td">faster</td>

      <td class="misc-table-td">takes an amount of time directly proportional to
      <strong>N</strong></td>

      <td class="misc-table-td">K * <strong>N</strong></td>
    </tr>

    <tr class="misc-table-tr-1">
      <td class="misc-table-td">logarithmic time</td>

      <td class="misc-table-td">much faster</td>

      <td class="misc-table-td">takes an amount of time proportional to the logarithm of
      <strong>N</strong></td>

      <td class="misc-table-td">K * log(<strong>N</strong>)</td>
    </tr>

    <tr class="misc-table-tr-2">
      <td class="misc-table-td">constant time</td>

      <td class="misc-table-td">fastest</td>

      <td class="misc-table-td">takes a fixed amount of time, no matter how large the input
      is</td>

      <td class="misc-table-td">K</td>
    </tr>
  </table>
  </div>
  </td>
  


  </tr>
  </table>
</body></html>
